0777. 在 LR 字符串中交换相邻字符【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 双指针

1. 📝 题目描述

• leetcode

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个 "LX" 替换一个 "XL"，或者用一个 "XR" 替换一个 "RX"。现给定起始字符串 start 和结束字符串 result，请编写代码，当且仅当存在一系列移动操作使得 start 可以转换成 result 时， 返回 True。

---

示例 1：

输入：start = "RXXLRXRXL", result = "XRLXXRRLX"
输出：true
解释：通过以下步骤我们可以将 start 转化为 result：
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

示例 2：

输入：start = "X", result = "L"
输出：false

---

提示：

• 1 <= start.length <= 10^4
• start.length == result.length
• start 和 result 都只包含 'L', 'R' 或 'X'。

2. 🎯 s.1 - 双指针

c

bool canTransform(char* start, char* end) {
    int n = strlen(start);
    int i = 0, j = 0;
    while (i < n || j < n) {
        while (i < n && start[i] == 'X') i++;
        while (j < n && end[j] == 'X') j++;
        if (i == n || j == n) return i == n && j == n;
        if (start[i] != end[j]) return false;
        if (start[i] == 'L' && i < j) return false;
        if (start[i] == 'R' && i > j) return false;
        i++; j++;
    }
    return true;
}

js

/**
 * @param {string} start
 * @param {string} end
 * @return {boolean}
 */
var canTransform = function (start, end) {
  const n = start.length
  let i = 0,
    j = 0
  while (i < n || j < n) {
    while (i < n && start[i] === 'X') i++
    while (j < n && end[j] === 'X') j++
    if (i === n || j === n) return i === n && j === n
    if (start[i] !== end[j]) return false
    if (start[i] === 'L' && i < j) return false
    if (start[i] === 'R' && i > j) return false
    i++
    j++
  }
  return true
}

py

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        n = len(start)
        i = j = 0
        while i < n or j < n:
            while i < n and start[i] == 'X': i += 1
            while j < n and end[j] == 'X': j += 1
            if (i == n) != (j == n): return False
            if i == n: return True
            if start[i] != end[j]: return False
            if start[i] == 'L' and i < j: return False
            if start[i] == 'R' and i > j: return False
            i += 1; j += 1
        return True

• 时间复杂度：$O(n)$，其中 n 是字符串长度
• 空间复杂度：$O(1)$

算法思路：

• 去掉 X 后两个字符串的 L、R 顺序必须一致
• L 只能左移，所以 start 中 L 的位置必须 >= end 中对应 L 的位置
• R 只能右移，所以 start 中 R 的位置必须 <= end 中对应 R 的位置